package compute.the.intersection.of.two.array;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @Time 2019/12/23
 * @author 王光浩
 * @Need 给出两个整型数组，找出两个数组中所有重复的元素（结果不去重）。比如num1数组为[1,2,2,3]，num2数组
 *       为[2,2],则最后结果为[2,2]
 * @Thinking 使用HashMap。使用HashMap将第一个数组中的内容加入到HashMap中，key值为数组元素值，value为该值
 *           出现的次数，然后遍历第二个数组，判断在HashMap中是否存在相同的元素值，如果存在则将该HashMap中
 *           该key对应的value-1（注意如果value为0——该key已经全部加入到结果集中，则继续循环），然后将对应的
 *           数组元素值加入结果集中。
 *           复杂度分析：时间复杂度O（n+m）——但是将数组1加入到HashMap中是存在HashMap的扩充；空间复杂度O（n）
 */
public class MyMethodTwo {
    public int[] intersect(int[] nums1, int[] nums2) {
    	Map<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
    	int[] result=new int[nums2.length];
    	int index=0;                             //保存下一个数据在result数组中的存放位置
    	//将第一个数组中的数据加入到HashMap中
    	for(int i:nums1) {
    		if(hashMap.containsKey(i)) {
    			hashMap.put(i, hashMap.get(i)+1); //如果先前存在该元素则将该元素的次数加一
    			continue;
    		}
    		hashMap.put(i, 1);
//    		hashMap.put(i, hashMap.getOrDefault(i, 0)+1);  一句顶万句
    	}
    	//将第二个数组中的重复元素找出，放在result数组中
    	for(int i:nums2) {
    		if(hashMap.containsKey(i) && hashMap.get(i)>0) {
    			result[index++]=i;
    			hashMap.put(i, hashMap.get(i)-1);
    		}
    	}
    	//将多余的部分截去
    	return Arrays.copyOf(result, index);
    }

}
